package offer.day19;

import java.util.LinkedList;
import java.util.Queue;

public class No32Second_PrintBinaryTreeFromTopToBottomByRow {
    /*
     *  面试题32从上到下打印二叉树
     * 题目二：分行从上到下导引二叉树
     * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印一行。
     * 例如：输入8->6   8->10 这样的二叉树，打印出8
     * 		6->5   6->7				  6  10
     * 		10->9  10->11			  5  7  9  11
     *
     *
     * 思路：在题目一的基础上（借助队列，首先将节点入队列，
     * 					循环中：记录当前这个队列的节点并从（头部）出队列，输出这个节点值，
     * 					并用之前记录的刚刚出队列的这个节点去进行判断，判断其左右子节点是否存在，存在则从（尾部）入队列
     * 					直到队列中已经没有数据了，）
     * 因为要进行分行打印，所以要加入两个标志位  toBePrinted 记录本行还剩下多少个元素没有打印
     * 									nextLine 记录下一行有多少要打印的元素
     *
     *
     * */
    public static void main(String[] args) {
        No32Second_PrintBinaryTreeFromTopToBottomByRow p = new No32Second_PrintBinaryTreeFromTopToBottomByRow();
        BinaryTreeNode root = new BinaryTreeNode(8);
        BinaryTreeNode one = new BinaryTreeNode(6);
        BinaryTreeNode two = new BinaryTreeNode(10);
        BinaryTreeNode three = new BinaryTreeNode(5);
        BinaryTreeNode four = new BinaryTreeNode(7);
        BinaryTreeNode five = new BinaryTreeNode(9);
        BinaryTreeNode six = new BinaryTreeNode(11);
        root.left = one;
        root.right = two;
        one.left = three;
        one.right = four;
        two.left = five;
        two.right = six;
        three.left = null;
        three.right = null;
        four.left = null;
        four.right = null;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        System.out.println("分行从上到下打印二叉树：");
        p.PrintBinaryTreeFromTopToBottomByRow(root);
    }

    private void PrintBinaryTreeFromTopToBottomByRow(BinaryTreeNode root) {
        if (root == null) return;

        Queue<BinaryTreeNode> queue = new LinkedList<>();
        int toBePrinted=1;
        int nextLine=0;
        queue.add(root);
        while (!queue.isEmpty()) {
            BinaryTreeNode tmp = queue.poll();
            System.out.println(tmp.val + " ");
            if(tmp.left!=null){
                queue.add(tmp.left);
                nextLine++;
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
                nextLine++;
            }
            toBePrinted--;
            if(toBePrinted==0){
                System.out.println();
                toBePrinted=nextLine;
                nextLine=0;
            }
        }

    }
}
